import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/10/16 下午 05:19
 */
public class day191016 {

    /**
     * 1.s1[i-1] == s2[j-1]，新增的两个字符相等的情况下，没有必要删除之前的结果，因此dp[i][j] = dp[i-1][j-1]
     * 2.s1[i-1] != s2[j-1]，取三者的最小值
     * （1）保留s2串，删除s1串的字符，dp[i][j] = dp[i-1][j] + s1.charAt(i-1)
     * （2）保留s1串，删除s2串的字符，dp[i][j] = dp[i][j-1] + s1.charAt(j-1)
     * （3）删除s1、s2串的字符，dp[i][j] = dp[i-1][j-1] + s1.charAt(i-1) + s2.charAt(j-1)
     *
     * @param s1
     * @param s2
     * @return
     */
    public int minimumDeleteSum(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = s1.length() - 1; i >= 0; i--) {
            dp[i][s2.length()] = dp[i + 1][s2.length()] + s1.codePointAt(i);
        }
        for (int i = s2.length() - 1; i >= 0; i--) {
            dp[s1.length()][i] = dp[s1.length()][i + 1] + s2.codePointAt(i);
        }
        for (int i = s1.length() - 1; i >= 0; i--) {
            for (int j = s2.length() - 1; j >= 0; j--) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j] + s1.codePointAt(i)
                            , dp[i][j + 1] + s2.codePointAt(j));
                }
            }
        }
        return dp[0][0];
    }

    public int minimumDeleteSum2(String s1, String s2) {
        int sum = 0;
        for (int i = 0; i < s1.length(); i++) {
            sum += s1.charAt(i);
        }
        for (int i = 0; i < s2.length(); i++) {
            sum += s2.charAt(i);
        }
        //dp[i][j]的意义,s1中以第i结尾,s2中以j结尾的最大Ascii值
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1) + s2.charAt(j - 1);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return sum - dp[s1.length()][s2.length()];
    }

    static class day191017 {

        int num = 0;

        public int countSubstrings(String s) {
            for (int i = 0; i < s.length(); i++) {
                //以当前点i位置，向两边扩展,以 i i+1位置向两边扩展
                count(s, i, i);
                count(s, i, i + 1);
            }
            return num;
        }

        private void count(String s, int start, int end) {
            //start往左边跑，end往右边跑，注意边界
            while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
                num++;
                start--;
                end++;
            }
        }

        public int countSubstrings2(String s) {
            // dp[i][j] 表示[i,j]的字符是否为回文子串
            boolean[][] dp = new boolean[s.length()][s.length()];
            int ret = 0;
            //自底向上 要判断 (i, j) 首先要知道 (i,j) 之间的 即(i + 1, j - 1)
            for (int i = s.length() - 1; i >= 0; i--) {
                for (int j = i; j < s.length(); j++) {
                    if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                        ret++;
                        dp[i][j] = true;
                    }
                }
            }
            return ret;
        }

    }

//    public static void main(String[] args) {
////        day191020 day191020 = new day191020();
////        day191020.removeSubfolders(new String[]{"/a", "/a/b", "/c/d", "/c/d/e", "/c/f"});
//        User user = new User("john@gmail.com", "1234");
//        System.out.println("Using orElse");
//        User result = Optional.ofNullable(user).orElse(createNewUser());
//        System.out.println("Using orElseGet");
//        User result2 = Optional.ofNullable(user).orElseGet(() -> createNewUser());
//
//    }

    private static User createNewUser() {
        System.out.println(("Creating New User"));
        return new User("extra@gmail.com", "1234");
    }

    static class User {

        private String email;

        private String name;

        public User(String email, String name) {
            this.email = email;
            this.name = name;
        }

        public String getEmail() {
            return email;
        }

        public void setEmail(String email) {
            this.email = email;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }
    }


    static class day191020 {
        public boolean checkStraightLine(int[][] coordinates) {
            if (coordinates.length <= 2) {
                return true;
            }
            int[] p1 = coordinates[0];
            int[] p2 = coordinates[1];
            for (int i = 2; i < coordinates.length; i++) {
                int[] coordinate = coordinates[i];
                boolean flag = (coordinate[0] - p1[0]) * (p1[1] - p2[1]) == (p1[0] - p2[0]) * (coordinate[1] - p1[1]);
                if (!flag) {
                    return false;
                }
            }
            return true;
        }

        public List<String> removeSubfolders(String[] folder) {
            List<String> ret = new ArrayList<>();
            Set<String> folders = new HashSet<>(Arrays.asList(folder));
            for (String f : folder) {
                String path = f;
                boolean flag = false;

                do {
                    path = removeLastDir(path);
                    flag = flag || folders.contains(path);
                } while (!path.isEmpty());

                if (!flag) {
                    ret.add(f);
                }
            }

            return ret;
        }

        private String removeLastDir(String path) {
            int index = path.lastIndexOf("/");
            return path.substring(0, index);
        }

        public int balancedString(String s) {
            int[][] map = new int[10005][4];
            for (int i = 0; i < s.length(); i++) {
                map[i + 1][0] = map[i][0];
                map[i + 1][1] = map[i][1];
                map[i + 1][2] = map[i][2];
                map[i + 1][3] = map[i][3];
                if (s.charAt(i) == 'Q') {
                    map[i + 1][0]++;
                }
                if (s.charAt(i) == 'W') {
                    map[i + 1][1]++;
                }
                if (s.charAt(i) == 'E') {
                    map[i + 1][2]++;
                }
                if (s.charAt(i) == 'R') {
                    map[i + 1][3]++;
                }
            }
            int ret = Integer.MAX_VALUE;
            for (int i = 0; i < s.length(); i++) {
                int low = i;
                int high = s.length() + 1;
                while (low < high) {
                    int mid = low + ((high - low) >> 1);
                    boolean flag = true;
                    for (int j = 0; j < 4; j++) {
                        if (map[s.length()][j] - map[mid][j] + map[i][j] > s.length() / 4) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        high = mid;
                    } else {
                        low = mid + 1;
                    }
                }
                if (low != s.length() + 1) {
                    ret = Math.min(ret, low - i);
                }
            }
            return ret;
        }

        class Job {
            int start, finish, profit;

            Job(int start, int finish, int profit) {
                this.start = start;
                this.finish = finish;
                this.profit = profit;
            }
        }

        class JobComparator implements Comparator<Job> {
            @Override
            public int compare(Job a, Job b) {
                return Integer.compare(a.finish, b.finish);
            }
        }

        public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
            Job[] jobs = new Job[startTime.length];
            for (int i = 0; i < jobs.length; i++) {
                jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
            }

            return schedule(jobs);
        }

        private int schedule(Job[] jobs) {
            Arrays.sort(jobs, new JobComparator());
            int length = jobs.length;
            int[] table = new int[length];
            table[0] = jobs[0].profit;

            for (int i = 1; i < length; i++) {
                int thisProfit = jobs[i].profit;
                int find = binarySearch(jobs, i);
                if (find != -1) {
                    thisProfit += table[find];
                }
                table[i] = Math.max(thisProfit, table[i - 1]);
            }
            return table[length - 1];
        }

        private int binarySearch(Job[] jobs, int index) {
            int low = 0, high = index - 1;
            while (low <= high) {
                int mid = low + ((high - low) >> 1);
                if (jobs[mid].finish <= jobs[index].start) {
                    if (jobs[mid + 1].finish <= jobs[index].start) {
                        low = mid + 1;
                    } else {
                        return mid;
                    }
                } else {
                    high = mid - 1;
                }
            }
            return -1;
        }
    }

    static class day191022 {
        public boolean divisorGame(int N) {
            boolean[] dp = new boolean[N + 1];
            for (int i = 2; i <= N; i++) {
                for (int j = 1; j < i; j++) {
                    if (i % j == 0 && !dp[i - j]) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[N];
        }

        /**
         * 思路：
         * <p>
         * 状态：dp[i][j]为s的从头开始到i的子字符串是否为t从头开始到j的子字符串的子序列
         * <p>
         * 状态转移公式：
         * <p>
         * 当char[i]==char[j]时，则字符i一定是j的子序列，如果0~i-1子字符串是0~j-1子字符串的子序列，则dp[i][j]=true，所以dp[i][j] = dp[i-1][j-1]；
         * 当char[i]!=char[i]时，即判断当前0~i子字符串是否是0~j-1的子字符串的子序列，即dp[i][j] = dp[i][j - 1]。如ab，eabc，虽然s的最后一个字符和t中最后一个字符不相等，但是因为ab是eab的子序列，所以ab也是eabc的子序列
         * 初始化：空字符串一定是t的子字符串的子序列，所以dp[0][j]=true
         * <p>
         * 结果：返回dp[sLen][tLen]
         * <p>
         * 作者：zxy0917
         * 链接：https://leetcode-cn.com/problems/is-subsequence/solution/java-dp-by-zxy0917-5/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         *
         * @param s
         * @param t
         * @return
         */
        public boolean isSubsequence(String s, String t) {
            if (s.length() == 0) {
                return true;
            }
            boolean[][] dp = new boolean[s.length() + 1][t.length() + 1];
            for (int i = 0; i < t.length(); i++) {
                dp[0][i] = true;
            }
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 1; j <= t.length(); j++) {
                    if (s.charAt(i - 1) == t.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = dp[i][j - 1];
                    }
                }
            }
            return dp[s.length()][t.length()];
        }

        public boolean isSubsequence2(String s, String t) {
            if (s.length() == 0) {
                return true;
            }
            int i = 0, j = 0;
            while (i < s.length() && j < t.length()) {
                if (s.charAt(i) == t.charAt(j)) {
                    i++;
                }
                j++;
            }
            return i == s.length();
        }
    }

    static class day191023 {
        public int minCostClimbingStairs(int[] cost) {
            int[] dp = Arrays.copyOf(cost, cost.length + 1);
            for (int i = 2; i <= cost.length; i++) {
                dp[i] = Math.min(dp[i - 2], dp[i - 1]) + dp[i];
            }
            return dp[cost.length];
        }

        public int maxProfit(int[] prices, int fee) {
            int[][] dp = new int[prices.length][2];
            dp[0][1] = -prices[0];
            for (int i = 1; i < prices.length; i++) {
                //表示没有股票在手时，身上含有的金额,状态的变化。 卖出
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
                //表示有股票在手时，含有的金额状态的变化  买入
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            }
            return dp[prices.length - 1][0];
        }

        public int maxProfit2(int[] prices, int fee) {
            int cash = 0, hold = -prices[0];
            for (int i = 1; i < prices.length; i++) {
                //卖出
                cash = Math.max(cash, hold + prices[i] - fee);
                //买入
                hold = Math.max(hold, cash - prices[i]);
            }
            return cash;
        }
    }

    static class day191024 {

        public int minFallingPathSum(int[][] A) {
            int[][] dp = new int[A.length + 1][A.length + 1];
            for (int i = 0; i < A.length; i++) {
                dp[0][i] = A[0][i];
            }
            for (int i = 1; i < A.length; i++) {
                for (int j = 0; j < A.length; j++) {
                    if (j == 0) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + A[i][j];
                    } else if (j == A.length - 1) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + A[i][j];
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j + 1], dp[i - 1][j - 1])) + A[i][j];
                    }
                }
            }
            int ret = Integer.MAX_VALUE;
            for (int i = 0; i < A.length; i++) {
                ret = Math.min(ret, dp[A.length - 1][i]);
            }
            return ret;
        }

        public int numberOfArithmeticSlices(int[] A) {
            if (A.length < 3) {
                return 0;
            }
            int ret = 0;
            int[] dp = new int[A.length + 1];
            for (int i = 2; i < A.length; i++) {
                if ((A[i - 1] - A[i - 2]) == (A[i] - A[i - 1])) {
                    dp[i] = dp[i - 1] + 1;
                } else {
                    dp[i] = dp[i - 1];
                }
                ret += dp[i];
            }
            return ret;
        }

        private int minDist = Integer.MAX_VALUE;

        public int minDistance(String word1, String word2) {
            lwstBt(word1, word2, 0, 0, 0);
            return minDist;
        }

        private void lwstBt(String word1, String word2, int i, int j, int eDist) {
            if (i == word1.length() || j == word2.length()) {
                if (i < word1.length()) {
                    eDist += (word1.length() - i);
                }
                if (j < word2.length()) {
                    eDist += (word2.length() - j);
                }
                minDist = Math.min(eDist, minDist);
                return;
            }
            if (word1.charAt(i) == word2.charAt(j)) {
                lwstBt(word1, word2, i + 1, j + 1, eDist);
            } else {
                lwstBt(word1, word2, i + 1, j, eDist + 1);
                lwstBt(word1, word2, i, j + 1, eDist + 1);
                lwstBt(word1, word2, i + 1, j + 1, eDist + 1);
            }
        }


        public int minDistance2(String word1, String word2) {
            if (word1.length() == 0 || word2.length() == 0) {
                return Math.max(word1.length(), word2.length());
            }
            int[][] dp = new int[word1.length()][word2.length()];
            for (int j = 0; j < word2.length(); j++) {
                if (word1.charAt(0) == word2.charAt(j)) {
                    dp[0][j] = j;
                } else if (j != 0){
                    dp[0][j] = dp[0][j - 1] + 1;
                } else {
                    dp[0][j] = 1;
                }
            }
            for (int i = 0; i < word1.length(); i++) {
                if (word1.charAt(i) == word2.charAt(0)) {
                    dp[i][0] = i;
                } else if (i != 0) {
                    dp[i][0] = dp[i - 1][0] + 1;
                } else {
                    dp[i][0] = 1;
                }
            }
            for (int i = 1; i < word1.length(); i++) {
                for (int j = 1; j < word2.length(); j++) {
                    if (word1.charAt(i) == word2.charAt(j)) {
                        dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1]));
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                    }
                }
            }
            return dp[word1.length() - 1][word2.length() - 1];
        }

        public int minDistance3(String word1, String word2) {
            int n1 = word1.length();
            int n2 = word2.length();
            int[][] dp = new int[n1 + 1][n2 + 1];
            // 第一行
            for (int j = 1; j <= n2; j++) {
                dp[0][j] = j;
            }
            // 第一列
            for (int i = 1; i <= n1; i++) {
                dp[i][0] = i;
            }

            for (int i = 1; i <= n1; i++) {
                for (int j = 1; j <= n2; j++) {
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + 1;
                    }
                }
            }
            return dp[n1][n2];
        }

    }

    public static void main(String[] args) {
        day191024 day191024 = new day191024();
        System.out.println(day191024.minDistance2("sea", "eat"));

        int i1 = Math.min(Math.min(3, 4), 5) + 1;
        int i2 = Math.min(5, Math.min(3, 4)) + 1;

        System.out.println(i1 + ":" + i2);
    }

}
